%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Public Key Cryptography}
\label{PublicKeyCryptography}

The theory of public key cryptography was introduced by Diffie and
Hellman in 1976. Public key cryptography does not displace symmetric
key cryptography --- they solve different problems.  The recent NIST
contest which resulted in the Advanced Encryption Standard did not
resulted in a new symmetric key, not public key standard.  Why?
Symmetric key algorithms do the bulk of encryption, and are orders
of magnitude faster than public key systems of comparable security.
They dispense with the restrictive conditions needed to build the
split of public and private keys, and focus on speed.  Public key
cryptography, on the other hand, solves the key exchange problem
--- how to establish a common key between two parties that may have
never met.  It also finds use in specialized algorithms for digital
signatures and message authentication.

The foundational concept of public key cryptography is that of the
invertible one-way function $f:X \rightarrow Y$ --- a function which
is efficiently computable on any value $x \in X$, but for which the
inverse is hard: given $y$ finding an $x$ such that $y = f(x)$ is
computationally hard.  Most public key systems rely on {\em trapdoor}
one-way functions.  For such a function the constructor of the
function has privileged information which allows the efficient
inversion of the function.

We begin with a description of symmetric and public protocols for
message exchange in order to understand the role of each in
cryptography.

\section{Public and Private Key Protocols}

We describe the standard symmetric and public key cryptography
protocols, then describe a hybrid protocol, which could be used
to exchange messages efficiently using public key cryptography for
key exchange and symmetric key encryption for the message content.
Each of these protocols describes the sequence of steps by which
Alice can send a secure message to Bob.  The word {\em public} or
{\em sends} refer to events or information to which an adversary
can have access.  The word {\em private} refers to information or
an exchange which is protected from eavesdropping.

\begin{center}
{\bf Symmetric Cryptography Protocol}

\begin{tabular}{ll}
\multicolumn{2}{l}{\em Initial setup:} \\
1. & Alice and Bob publicly agree on a cryptosystem.\\
\multicolumn{2}{l}
   {\em For each message Alice $\rightarrow$ Bob:}\\
1. & Alice and Bob privately agree on a key.\\
2. & Alice enciphers her plaintext using the agreed key.\\
3. & Alice sends the ciphertext message to Bob.\\
4. & Bob deciphers the ciphertext message to obtain the plaintext.
\end{tabular}
\end{center}

The need to exchange keys for every exchange was a critical problem
prior to the theoretical solution with public key cryptography by
Diffie and Hellman.  The public key protocol proceeds as follows,
requiring only one initial public key exchange.

\begin{center}
{\bf Public Key Cryptography Protocol}

\begin{tabular}{ll}
\multicolumn{2}{l}{\em Initial setup:} \\
1. & Alice and Bob publicly agree on a cryptosystem. \\
2. & Bob sends Alice his public key. \\
\multicolumn{2}{l}{\em For each message Alice $\rightarrow$ Bob:}\\
1. & Alice enciphers her plaintext using Bob's public key.\\
2. & Alice sends the ciphertext message to Bob.\\
3. & Bob deciphers the ciphertext message using his private key.
\end{tabular}
\end{center}

As noted in the preceding discussion, public key cryptosystems
are several orders of magnitude slower than comparable symmetric
key cryptosystems.  Moreover, a public key cryptosystem is
susceptible to chosen plaintext attacks: an adversary can create a
lookup table of pairs $(E_K(M),M)$ for the known public key $K$.
Therefore the amount of public key ciphertext which is transmitted
should be strictly limited.

These considerations lead to the following hybrid protocol, in which
the public key cryptosystem is used for key exchange and a fast
symmetric key cryptosystem is used for message encryption.

\begin{center}
{\bf Hybrid Cryptographic Protocol}

\begin{tabular}{ll}
\multicolumn{2}{l}{\em Initial setup:} \\
1. & \begin{minipage}[t]{12cm}
     {Alice and Bob publicly agree on a public key cryptosystem
     and a symmetric key cryptosystem.}
     \end{minipage}\\
2. & Bob sends Alice his public key. \\
\multicolumn{2}{l}{\em For each message Alice $\rightarrow$ Bob:}\\
1. & Alice generates a random session key $K$.\\
2. & Alice enciphers $K$ using Bob's public key.\\
3. & Alice enciphers the plaintext message using $K$.\\
4. & \begin{minipage}[t]{12cm}
     Alice sends Bob the enciphered session key and
     the ciphertext message.
     \end{minipage}\\
5. & \begin{minipage}[t]{12cm}
     Bob deciphers the enciphered session key using his private key.
     \end{minipage}\\
6. & Bob deciphers the ciphertext message using the session key.
\end{tabular}
\end{center}

An additional layer can be added to the hybrid exchange, involving
a trusted authority, which carries out the function of certifying
the identity of individuals and their public keys, managing a
database of public keys, and handling expiration of public keys.
The public key exchange step, in which Bob sends Alice his public
key, in the hybrid protocol can therefore be replaced with any of
the following:
\begin{center}
%\renewcommand{\tmp}{\arraystretch}
%\renewcommand{\arraystretch}{1.25}
\begin{tabular}{l}
$\bullet$ Alice gets Bob's key from Bob.\\
$\bullet$ Alice gets Bob's key from a trusted authority's database.\\
$\bullet$ Alice gets Bob's key from her private database.
\end{tabular}
%\renewcommand{\arraystretch}{\tmp}
\end{center}
\vspace{4mm}

\begin{center}
{\large\bf Trapdoor one-way functions}
\end{center}

Several years elapsed between when Diffie and Hellman presented their
{\em New directions in cryptography} with the theory of public key
cryptography based on trapdoor one-way functions, and the discovery
of a practical example of trapdoor one-way functions for cryptographic
use.  The principal public key cryptosystems in use today, based on
trapdoor one-way functions, are the RSA cryptosystem and the ElGamal
cryptosystem.
We describe the underlying mathematical functions used in the RSA and
ElGamal constructions.
\vspace{4mm}

\noindent{\bf RSA}.

The trapdoor one-way function used in RSA is a fixed exponentiation
in $\Z/n\Z$ for a composite integer $n$.
$$
\SelectTips{cm}{10}
\xymatrix@R=1mm@C=2mm{
\Z/n\Z \ar@{->}[rr]  && \Z/n\Z\\
    m  \ar@{|->}[rr] &&    m^e}
$$
The public data is the exponent $e$ and the modulus $n$, which is
presumed to be of the form $pq$ for distinct primes $p$ and $q$.
The presumed difficulty of inverting this function is based on the
difficulty of factoring $n$, or on the difficulty of a weaker problem
version called the RSA problem.  The trapdoor for this function is
the knowledge of the factorization of $n$.
\vspace{4mm}

\noindent{\bf ElGamal}.

The ElGamal function is based on the exponentiation of a fixed
multiplicative generator $a$ for $\F_p^*$, the group of nonzero
elements of the finite field of $p$ elements.  The map takes $m$
to the power $a^m \bmod p$:
$$
\SelectTips{cm}{10}
\xymatrix@R=1mm@C=2mm{
\Z/(p-1)\Z \ar@{->}[rr]  && \F_p^*\\
    m  \ar@{|->}[rr] &&    a^m}
$$
The public data is the generator $a$ and the prime $p$, and inverting
the cryptographic function is solved by the discrete logarithm problem
-- finding $m$ given $a$ and $a^m$, or on a weaker problem called the
Diffie Hellman problem.
\vspace{4mm}

\noindent{\bf Elliptic Curves}.

Alternatively, the ElGamal construction can be solved using the
discrete logarithm problem on an elliptic curve $E$ over a finite
field $\F_q$.  An elliptic curve is defined by an equation of the
form
$$
y^2 + (a_1x + a_3)y = x^3 + a_2 x^2 + a_4 x + a_6
$$
with fixed coefficients $a_1,a_2,a_3,a_4,a_6$ in $\F_q$.  The set
$E(\F_q)$ of points $(x,y)$ in $\F_q^2$ solving this equation plus
a distinguished point $O$ at infinity forms a group law under an
addition, which we denote $+$.  For groups $E(\F_q)$ and $\F_p^*$
of comparable size, the discrete logarithm problem on the elliptic
curve is believed to be a harder problem than the classical one
in $\F_p^*$.  Elliptic curves will not be a topic of discussion in
this book, but are becoming commonplace in implementations of
smart cards and cryptography for low-power devices.

%\begin{center}{\Large\bf MATH3024: Lecture 19}\end{center}

\section{RSA Cryptosystems}

The RSA cryptosystem is based on the difficulty of finding an inverse
to exponentiation by a fixed $e$ on $\Z/n\Z$ for composite $n$, applied
for $n$ equal to a product of two large primes $p$ and $q$.
An efficient solution to integer factorization, or a solution to the
possibly weaker {\em RSA problem} would render the RSA cryptosystem
insecure.  The trapdoor for RSA encryption is the knowledge of the prime
factors of $n$ (which allows the determination of an inverse deciphering
exponent $d$ for any enciphering exponent $e$).

{\bf RSA Problem}. Given integers $e$ and $n = pq$ such that
$\GCD(e,p-1) = \GCD(e,q-1) = 1$, and an integer $c$, find an $m$
such that $c = m^e \bmod n$.

{\bf Rule:}
Let $p$ be a prime, then the reduction $m^x \bmod p$ remains unchanged
whenever
\begin{center}
\begin{tabular}{ll}
(a) $m$ is changed by a multiple of $p$, or \\
(b) $x$ is changed by a multiple of $p-1.$
\end{tabular}
\end{center}
We apply this rule in the RSA algorithm for $x \equiv 1 \bmod p-1$ to
conclude that $m = m^x \bmod p$.

{\bf RSA Protocol}

\begin{tabular}{ll}
\multicolumn{2}{l}
   {\begin{minipage}[t]{13cm}
    Public key: $(e,n)$ where $n = pq$ for two large primes
    $p$ and $q$ such that $\GCD(e,p-1) = \GCD(e,q-1) = 1$.
    \end{minipage}}\\
\multicolumn{2}{l}
   {\begin{minipage}[t]{13cm}
    Private key: $(d,n)$ where $ed \equiv 1 \bmod (p-1)$ and
    $ed \equiv 1 \bmod (q-1)$.
    \end{minipage}}\\
\multicolumn{2}{l}{\em Initial setup:} \\
1. & Alice obtains Bob's public key $(e,n)$.\\
\multicolumn{2}{l}
   {\em For each message $m$ Alice $\rightarrow$ Bob:}\\
1. & Alice computes $c = m^e \bmod n$.\\
2. & Alice sends the ciphertext message $c$ to Bob.\\
3. & Bob deciphers the ciphertext message as $m = c^d \bmod n$.
\end{tabular}
\vspace{2mm}

The correctness of the deciphering follows from the construction
of $d$ such that $ed \equiv 1 \bmod n$.  By the above rule, it
follows that
$$
m \equiv m^{ed} \bmod p \hbox{ and } m \equiv m^{ed} \bmod q,
$$
from which it follows that $m = m^{ed} \bmod pq$.

\noindent
{\bf Example.}
Let $p = 11$ and $q = 23$, so $n = 253$, and $e = 3$.  We verify that
$\GCD(e,p-1)=1$ and $\GCD(e,q-1)=1$.  Suppose that the ciphertext is
$c = 29$ in $\Z/253\Z$.  To construct the inverse of exponentiation by
$e$, we need to find $d_1$ and $d_2$ such that
$$
\begin{array}{l}
e\,d_1 \equiv 1 \bmod (p-1)\\
e\,d_2 \equiv 1 \bmod (q-1)\\
\end{array}
$$
First we compute the extended GCD's of the pairs $(e,p-1) = (3,10)$ and
$(e,q-1) = (3,22)$.  These are given by the relations:
$$
\begin{array}{l}
-3 \cdot 3 + 1 \cdot 10 = 1\\
-7 \cdot 3 + 1 \cdot 22 = 1\\
\end{array}
$$
giving the equalities $-3 e \equiv 1 \bmod 10$ and $-7 e \equiv 1
\bmod 22$.  Therefore if $e d_1 \equiv 1 \bmod 10$, then we have
$$
d_1 \equiv (-3\,e)\,d_1 \bmod 10
    \equiv -3\,(e\,d_1) \bmod 10
    \equiv -3 \bmod 10 \equiv 7 \bmod 10.
$$
Similarly if $e d_2 \equiv 1 \bmod 22$, then we have
$$
d_2 \equiv (-7\,e)\,d_2 \bmod 22
    \equiv -7 (e\,d_2) \bmod 22
    \equiv -7 \bmod 22 \equiv 15 \bmod 22.
$$
Now we can compute the plaintext message $m$ such that $c = m^3 \bmod 253$.
First we compute
\begin{multline*}
m_1 = c^{d_1} \bmod 11 \equiv 7^7 \bmod 11
  \equiv 7^4\,7^2\,7 \bmod 11 \\
  \equiv 3\cdot 5\cdot 7 \bmod 11
  \equiv 3 \cdot 2 \bmod 11 \equiv 6 \bmod 11,
\end{multline*}
and similarly
\begin{multline*}
m_2 = c^{d_2} \bmod 23 \equiv 6^{15} \bmod 23 \\
       \equiv 6^8\,6^4\,6^2\,6 \bmod 23
       \equiv (-5\cdot 8)\,(13\cdot 6) \bmod 23 \\
       \equiv 6\cdot 9 \bmod 23 \equiv 8 \bmod 23.
\end{multline*}
Now we can combine $m_1 = 6 \bmod 11$ and $m_2 = 8 \bmod 23$ by the
Chinese remainder theorem.  We expressed the extended GCD of 11 and
23 as:
$$
r p + s q = -2 \cdot 11 + 1 \cdot 23 = 1.
$$
Setting $m = m_2 + k q$, we find $m_1 = (m_2 + k q) \bmod p$, whence
$$
s (m_1-m_2) \equiv s (k\,q) \bmod p
    \equiv k (s\,q) \bmod p \equiv k \bmod p.
$$
So we have solved for $k \equiv s(m_1-m_2) \bmod p \equiv 1\,(6-8)
\equiv -2 \bmod p$.  Therefore $m \equiv m_1 + k q \bmod 253
\equiv 6 - 46 \bmod 253 \equiv 213 \bmod 253$.

{\bf RSA with exponent 3}.
A commonly used exponent for RSA encryption is $e = 3$.  This
allows efficient enciphering using only two arithmetic operations
(two multiplications or one squaring and one multiplication).
No such gain is achieved for deciphering.

However, this presents algorithm presents the following problem for
security.  Let $m$ be a message to be sent to three parties, with
RSA moduli $n_1$, $n_2$, and $n_3$.  The encoding of the message
satisfies $0 \le m \lt n_i$.  By means of the Chinese remainder
theorem, we can recover $c = m^3 \bmod n_1 n_2 n_3$ from the three
enciphered messages $c_1 = m^3 \bmod n_1$, $c_2 = m^3 \bmod n_2$,
and $c_3 = m^3 \bmod n_3$.  While the latter messages $c_i$, as
the modular representatives of some huge integer, appear random.
But from the bounds on $m$, the cube satisfies the bound:
$$
0 \le m^3 \lt n_1 n_2 n_3,
$$
hence the smallest modular representative $c$ equals $m^3$, and
the cube root can be extracted as an integer to recover $m$.

A valid protocol to overcome this dilemma, for $e = 3$, is to never
send the same message to more than one party.  This is achieved by
adding unique random padding to every message prior to enciphering.
This turns the message $m$ into three distinct messages $m_1$,
$m_2$, and $m_3$.  The Chinese remainder theorem then solves for
some integer
$$
0 \le c \lt n_1 n_2 n_3
$$
such that $c \equiv m_i \bmod n_i$, but this integer no longer bears
any relation to any cube $m^3$.

%\begin{center}{\Large\bf MATH3024: Lecture 20}\end{center}

\section{ElGamal Cryptosystems}

The ElGamal Cryptosystem is implicitly based on the difficultly
of finding a solution to the discrete logarithm in $\F_p^*$: given
a primitive element $a$ of $\F_p^*$ and another element $b$, the
discrete logarithm problem (DLP) is the computational problem of
finding $x = \log_a(b)$  such that $b = a^x$.

Efficient algorithms for the discrete logarithm problem would render
the ElGamal Cryptosystem insecure, the possibly weaker Diffie-Hellman
problem (DHP) is the precise problem on which the cryptosystem is
based: given $b = a^x$ and $c = a^y$ in $\F_p^*$, compute $a^{xy}$.

Note that $a^{xy}$ can not be formed as any obvious algebraic
combination of $a^x$ and $a^y$ like $a^x a^y = a^{x+y}$.
In fact, other cryptosystems rely on the difficult of the Decision
Diffie-Hellman problem (DDHP) being hard: given $a^x$, $a^y$ and $c$,
decide whether or not $c = a^{xy}$.  Both the DHP and the DDHP are
easy if the DLP is easy.

{\em Definition.} Recall that an element $a$ of $\F_p^*$ is said to be
{\em primitive} if and only if
$$
1,a,a^2,\dots,a^{p-2}
$$
are all distinct.  Primitive elements always exist in any finite field.

{\bf ElGamal Protocol}

\begin{tabular}{ll}
\multicolumn{2}{l}
   {\begin{minipage}[t]{13cm}
    Public key: $(a,a^x,p)$ where $p$ is a prime, $a$ is a primitive
    element of $\F_p^*$, and $x$ is an integer $1 \le x \lt p-1$.
    \end{minipage}}\\
\multicolumn{2}{l}
   {\begin{minipage}[t]{13cm}
    Private key: The integer $x$.
    \end{minipage}}\\
\multicolumn{2}{l}{\em Initial setup:} \\
1. & Alice obtains Bob's public key $(a,a^x,p)$.\\
\multicolumn{2}{l}
   {\em For each message $m$ Alice $\rightarrow$ Bob:}\\
1. & Alice chooses a private element $y$ randomly in $1 \le y \lt p-1$.\\
1. & Alice computes $r = a^y$ and $s = m a^{xy}$. \\
2. & Alice sends the ciphertext message $c = (r,s)$ to Bob.\\
3. & Bob deciphers the ciphertext message as $m = r^{-x}s \bmod p$.
\end{tabular}
\vspace{0.2cm}

The correctness of the deciphering is verified as follows:
$$
r^{-x} s = (a^y)^{-x} m a^{xy} = m a^{-yx}a^{xy} = m a^{xy-yx} = m.
$$

\begin{center}
{\large\bf Discrete Logarithms}
\end{center}

The main known attack on an ElGamal cryptosystem is to solve the
discrete logarithm problem: given both $a$ and $a^x$ (in the finite
field $\F_p$), find the value for $x$.
In order for the discrete logarithm problem (DLP) to be hard, it is
not enough to choose any prime $p$.
One needs to select a prime $p$ such that $p-1$ has a large prime factor.
Suppose, on the contrary, that $p-1$ is divisible only by primes less
than some positive integer $B$.  Such a number is said to be $B$-smooth.
The DLP can be reduced to solving a small number of discrete logarithm
problems of ``size'' $B$ rather than of size $p-1$.

As an example, let $r$ be a prime divisor of $p-1$, and let $m = (p-1)/r$.
Suppose that we want to solve for $x$ such that $b = a^x$.  The exponent
is defined up to multiples of $p-1$.  If we raise both sides to the power
$m$, then for the problem $b^m = a^{mx}$ a solution $x$ is well-defined
up to multiples of $r$:
$$
a^{m(x+r)} = a^{mx+mr} = a^{mx}a^{p-1} = a^{mx},
$$
since $a^{p-1} = 1$.

If we now find that $p-1 = r_1 r_2 \cdots r_t$ for pairwise distinct
primes $r_i$, the by the Chinese remainder theorem the value of
$x \bmod p-1$ can be determined from its modular values $x \bmod r_i$,
for all $1 \le i \le t$.  So the hardness of the DLP determined by
the size of the largest prime divisor of $p-1$.

\noindent{\bf Exercise.}
Suppose that a prime power $r^k$ divides $p-1$.  How would you solve
the DLP for $x \bmod r^k$?

\begin{center}
{\large\bf Algorithmic Considerations}
\end{center}

A na\"{\i}ve algorithm for solving the discrete logarithm problem for
$\log_a(b)$ is to compute $1,a,a^2,\dots$ until a match is found with
$b$.  As we have just seen, it is possible to replace $a$ with $a_1 =
a^m$ and $b$ with $b_1 = b^m$ in order to solve $\log_{a_1}(b_1)$
modulo $r$ such that $rm = p-1$.  In this way we have to build the
list $1,a_1,a_1^2,\dots,a_1^x$ of length at most $r$ before finding
$b_1$.

An alternative approach is called the baby-step, giant-step method.
We set $s = [\sqrt{r}]+1$ and to form a first list $1,a_1,a_1^2,\dots,
a_1^{s-1}$ of length $s$, called the baby steps, then form the second
list $b_1,a_1^sb_1,a_1^{2s}b_1,\dots,a_1^{s^2}b_1$ of giant steps,
to find a match.

If a match is found, say $a_1^i = b_1 a_1^{js}$, then we have found
$b_1 = a_1^{i-js}$, so $x = i-js \bmod r$.  On the other hand, if
$x$ is a solution to the DLP $\bmod r$, then we can write $x = i-js$
for some $0 \le i, -j \le s$, so the above algorithm finds a match.

%\begin{center}{\Large\bf MATH3024: Lecture 21}\end{center}

\section{Diffie--Hellman Key Exchange}

Diffie and Hellman proposed the following scheme for establishing
a common key.  The scheme is widely used because of the simplicity of
its implementation, however an naive implementation without identity
authentication leaves the protocol subject to a man-in-the-middle
attack.

1. $A$ and $B$ decide on a large prime number $p$ and a primitive
element $a$ of $\Z/p\Z$, both of which can be made public.

2. $A$ chooses a secret random $x$ with $\GCD(x,p-1) = 1$ and $B$
chooses a secret random $y$ with $\GCD(y,p-1) = 1$.

3. $A$ sends Bob $a^x \bmod p$ and Bob sends Alice $a^y \bmod p$.

4. Each is able to compute a session key $K = a^{xy} = (a^x)^y
= (a^y)^x$.

An eavesdropper only has knowledge of $p$, $a$, $a^x$ and $a^y$,
and would need to break the Diffie-Hellman problem to be able to
come up with the session key.

\begin{center}
{\large\bf Man in the Middle Attack}
\end{center}

The man-in-the-middle attack is a protocol for an eavesdropper
$E$ to intercept a message exchange between $A$ and $B$. The attack
is premised on a Diffie-Hellman key exchange, but the principle
applied to any public key cryptosystem for which the keys used for
public key exchange is not certified with a certification authority.

We assume that $A$ and $B$ have agreed on a prime $p$ and a
primitive element $a$ of $\Z/p\Z$, and that $E$ is positioned
between $A$ and $B$.  Having observed this Diffie-Hellman
initialization $E$ prepares for the man-in-the-middle attack.

1. $A$ chooses a secret key $x$, creates a public key $a^x$, and
sends it to $B$, which is intercepted by~$E$.

2. $E$ chooses a private integer $z$ at random, and creates the
alternative public key $a^z$ which she sends to $B$, pretending
to be $A$.  At the same time she sends same key $a^z$ to $A$,
now posing as $B$.

3. Now $E$ has established a common session key $a^{xz}$ with
$A$ and common session key $a^{yz}$ with $B$.  Message exchanges
between $A$ and $B$ pass through $E$ and can be deciphered, read,
modified, re-enciphered, and resent in transit.

The breakdown of the key exchange protocol is due to lack of
identity authentication of the communicating parties.  If, for
instance the public key $(a,a^x,p)$ of $A$ could be confirmed
with an independent certification authority, then $B$ would not
have confused $E$ with $A$.

\section*{Exercises}

\input{exercises/PublicKeyCryptography}
